package com.buddy.learn.algorithm.simple;

import java.util.*;

/**
 * 二叉树
 * 二叉树与数组：
 * 使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上，
 * 如果某一个节点的 Left 或者 Right 空缺，则数组的位置也会相应的空出来
 * <p>
 * parent 的 Left index = 2*parent+1 ；Right index=2*parent+2
 * leftChild 的 parent = (leftChild -1)/2
 *
 * @author Buddy
 * @date 2021/4/20
 */
public class _二叉树右视图 {

    private class Node {
        int data;
        Node left;
        Node right;

        Node(int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    private Node init() {
        // 必须逆序建立，因为上面的节点会用到下面的子节点
        Node N = new Node(7, null, null);
        Node H = new Node(6, null, null);
        Node E = new Node(5, H, N);
        Node D = new Node(4, null, null);
        Node C = new Node(3, null, null);
        Node B = new Node(2, D, E);
        Node A = new Node(1, B, C);
        return A;
    }


    public static void main(String[] args) {
        _二叉树右视图 binaryTree = new _二叉树右视图();
        Node root = binaryTree.init();
        System.out.println(rightSideView(root));
    }

    /**
     * 二叉树右视图：
     * 广度优先，使用队列
     * 对二叉树进行层次遍历，只保留最右侧节点
     */
    private static List<Integer> rightSideView(Node root) {
        // 保留每一层的最右侧元素
        Map<Integer, Integer> cache = new HashMap<>();

        Queue<Node> queue = new LinkedList<>();
        Queue<Integer> depthQueue = new LinkedList<>();

        int maxDepth = -1;

        queue.add(root);
        depthQueue.add(0);
        while (!queue.isEmpty()) {
            Node node = queue.remove();
            int depth = depthQueue.remove();
            if (node != null) {
                // 维护二叉树的最大深度
                maxDepth = Math.max(maxDepth, depth);

                // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                cache.put(depth, node.data);

                queue.add(node.left);
                queue.add(node.right);
                depthQueue.add(depth + 1);
                depthQueue.add(depth + 1);
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int depth = 0; depth <= maxDepth; depth++) {
            res.add(cache.get(depth));
        }
        return res;
    }


}
